오늘은 B-Tree에서 키값을 제거하는 Delete에 대해서 이야기 하도록 하겠다. 여느 때와 마찬가지로, Wikipedia1를 기준으로 설명하겠다.
B-Tree에서 Delete 작업을 수행하는 데에는 2가지의 잘 알려진 방식이 존재한다. 여기서는 키값을 찾아낸 뒤 제거한 후, 트리의 구조를 재구성하는 방식의 알고리즘을 설명한다.
어떤 요소를 제거할 때에는 2가지 특수한 경우가 발생한다.
내부 노드의 제거하려는 요소가 자식 노드의 separator 역할을 수행한다.
어떤 요소를 제거하면 그 노드의 요소나 자식 노드의 개수가 최소 개수보다 더 적어진게 된다.
아래는 이러한 경우들에 대하여 삭제를 진행하는 방법이다.
삭제할 키값을 Search 한다.
그 값이 리프 노드에 있을 경우, 그 노드에서 해당 키값을 제거한다.
만약 언더플로우가 발생하면, “삭제 후 리밸런싱” 항목에 따라 트리를 리밸런싱한다.
내부 노드의 각 요소들은 2개의 subtree들에 대하여 separation value의 역할을 하기 때문에, 내부 노드에서 어떤 요소의 삭제가 일어날 때, 기존 sperator의 대체제를 찾아야 한다.
왼쪽 subtree에서는 가장 큰 요소라 하더라도 그 seperator보다는 작고, 오른쪽 subtree에서는 가장 작은 요소라 하더라도 그 sperator보다는 크다는 사실을 기억하라. 이 두 요소 모두 리프 노드에 존해하며, 둘 중 하나의 원소가 두 subtree의 새로운 separtor가 될 수 있다.
알고리즘은 다음과 같다.
왼쪽 subtree의 가장 큰 요소나 오른쪽 subtree의 가장 작은 요소 중 하나를 새로운 separator로 선택하고, 선택된 그 요소를 원래 있던 리프노드에서 제거한 뒤, 기존의 separator를 대체한다.
1번에서 기존의 separator를 대체하던 중 리프 노드에서 새로운 separator가 삭제되었다. 이 때 해당 리프 노드가 가져야 할 최소 요소의 개수보다 적은 요소를 가지게 되면, 그 리프 노드에서 부터 리밸런싱을 시작한다.
리밸런싱은 리프 노드에서 시작하여 루트 노드로 올라가는 방향으로 진행되며 해당 트리가 균형을 되찾을 때까지 진행된다. 한 노드에서 하나 요소가 삭제되어 그 노드의 요소의 개수가 가질 수 있는 최소한의 개수보다 적어지게 되면, 몇몇 원소들은 모든 노드들이 최소 개수 이상의 요소를 가지게 하기 위해 재분배되어야 한다.
대개, 재분배는 최소 필요 개수를 초과하는 수의 요소를 가진 형제 노드에서 요소를 움직이는 과정을 수반한다. 이러한 재분배 작업을 ‘회전’이라고 부른다. 만약 어떠한 형제 노드에서도 요소를 가져올 수 없다면, 그 요소의 수가 부족한 노드는 형제 노드와 합쳐져야 한다.
합치는 과정은 부모 노드가 separtor 요소를 잃게 만들고, 그 결과로 부모 노드 또한 리밸런싱이 필요해질 수 있다. 이 과정은 루트 노드까지 계속 진행될 수도 있다.
최소 요소 개수 제한은 루트 노드에 적용되지 않으므로, 루트 노드만을 요소의 개수가 부족한 노드로 만드는 것은 문제가 되지 않는다.
리밸런싱 알고리즘은 다음과 같다.
요소의 수가 부족해진 노드의 오른쪽 형제 노드가 최소 필요 개수를 초과할 경우, 왼쪽 방향으로 회전시킨다.
부모 노드의 separator를 복사하여 요소의 개수가 부족한 노드에 맨 끝에 삽입한다.
부모 노드의 separtor를 오른쪽 형제 노드의 첫 번째 원소로 대체한다.
트리는 균형을 되찾게 된다.
요소의 수가 부족해진 노드의 왼쪽 형제 노드가 최소 필요 개수를 초과할 경우, 오른쪽 방향으로 회전시킨다.
부모 노드의 separator를 복사하여 요소의 개수가 부족한 노드에 시작 부분에 삽입한다.
부모 노드의 separator를 왼쪽 형제 노드의 마지막 원소로 대체한다.
트리는 균형을 되찾게 된다.
양쪽의 형제 노드 모두 최소한의 요소 개수만을 가지고 있다면, separator를 둘러싸는 한 형제 노드와 합친다.
separator를 ‘왼쪽’ 노드의 끝에 삽입한다. 이 때 ‘왼쪽’의 의미는 요소의 개수의 부족한 노드와 그 노드의 왼쪽에 있는 형제 노드 둘 중 어느 것도 될 수 있다.
‘오른쪽’ 노드에 있는 모든 원소들을 왼쪽 노드에 삽입한다.
부모 노드의 separator와 함께 텅 빈 ‘오른쪽’ 노드를 제거한다. 이 때, 부모 노드의 요소가 하나 감소한다.
만약 부모 노드가 루트 노드이고, 텅 빈 노드가 되었다면, 합쳐진 노드를 새로운 루트 노드로 삼는다. 이 때, 트리의 높이가 줄어들게 된다.
그렇지 않고, 부모 노드가 요소의 개수가 최소 필요 개수보다 적어지게 된다면, 부모 노드에서 다시 리밸런싱을 진행한다.
원래대로라면 준비해온 이미지와 함께 실제로 삭제가 어떻게 일어나는지 따라가봐야 하지만, 오늘은 시간이 많이 늦어서 이미지를 준비해오지 못했다. 내일 글에서 이 부분은 다시 다루도록 하겠다.
오늘의 개발은 여기까지!
1: https://en.wikipedia.org/wiki/B-tree